package com.leetcode.algorithm.y22.m07;

import java.util.ArrayList;
import java.util.List;

/**
 * 556. 下一个更大元素 III
 * 
 * https://leetcode.cn/problems/next-greater-element-iii/
 * 
 * @author jie.deng
 *
 */
public class Question0556Solution01 {

	public int nextGreaterElement(int n) {
		// 获取每一位的数字
		List<Integer> list = new ArrayList<>();
		int num = n;
		while (num > 0) {
			list.add(num % 10);
			num /= 10;
		}

		// 完全逆序数没有下一个更大数，找第一个正序数
		int len = list.size();
		int idx = 0;
		int greaterBitNum = list.get(idx);
		for (idx = 1; idx < len; idx++) {
			int nextNum = list.get(idx).intValue();
			if (nextNum < greaterBitNum) {
				break;
			} else {
				greaterBitNum = nextNum;
			}
		}
		if (idx == len) {
			return -1;
		}

		// 交换第0-idx-1位中第一个比第idx位大的位和第idx位
		int idxNum = list.get(idx);
		for (int i = 0; i <= idx - 1; i++) {
			int tmp = list.get(i).intValue();
			if (tmp > idxNum) {
				list.set(idx, tmp);
				list.set(i, idxNum);
				break;
			}
		}

		long ret = 0;
		for (int i = len - 1; i >= idx; i--) {
			ret *= 10;
			ret += list.get(i);
		}
		for (int i = 0; i < idx; i++) {
			ret *= 10;
			ret += list.get(i);
		}
		return ret > Integer.MAX_VALUE || ret == n ? -1 : (int) ret;
	}

}
